package LeetCode.LeetCode2;

/**
 * 斐波那契数
 * @author lumin
 * @date 2022/03/23 19:15
 **/
public class Num509 {
    //递归
//    public int fib(int n) {
//        if(n == 0){
//            return 0;
//        }
//        if(n == 1){
//            return 1;
//        }
//        return fib(n - 1) + fib(n - 2);
//    }
    //动态规划
    public int fib(int n){
        if(n < 2){
            return n;
        }
        int p = 0;
        int q = 0;
        int sum = 1;
        for (int i = 2; i <= n; i++) {
            p = q;
            q = sum;
            sum = p + q;
        }
        return q;
    }
}